//75
class Solution {
    public void sortColors(int[] nums) {
        quiclySort(nums, 0, nums.length-1);
    }

    public void quiclySort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        //利用三数取中法优化快排
        int m = mid(nums, l, r);
        sweap(nums, l, m);
        m = l;
        l++;
        
        m = sort(nums, l, r, m);
        
        quiclySort(nums, l-1, m-1);
        quiclySort(nums, m+1, r);
    }

    public int sort(int[] nums, int l, int r, int m) {
        while (l < r) {
            while (l < r && nums[m] < nums[r]) {
                r--;
            }
            while (l < r && nums[m] >= nums[l]) {
                l++;
            }
            sweap(nums, l, r);
        }
        if (nums[l] < nums[m]) {
            sweap(nums, l, m);
        }
        return l;
    }

    public void sweap(int[] nums, int l, int r) {
        int tmp = nums[l] ^ nums[r];
        nums[l] = tmp ^ nums[l];
        nums[r] = tmp ^ nums[l];
    }

    public int mid(int[] nums, int l, int r) {
        if (nums[l] < nums[r]) {
            return nums[l] < nums[(l+r)/2] ? (nums[r] < nums[(l+r)/2] ? r : (l+r)/2) : l;
        }
        else {
            return nums[l] < nums[(l+r)/2] ? l : (nums[r] > nums[(l+r)/2] ? r : (l+r)/2);
        }
    }
}
//1419
class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        int len = croakOfFrogs.length();
        char[] arr = {'c', 'r', 'o', 'a', 'k'};
        int[] ret = new int[5];
        int max = 0;
        for (int i = 0; i < len; i++) {
            char c = croakOfFrogs.charAt(i);
            switch(c) {
                case 'c':
                ret[0]++;
                max = Math.max(max, ret[0]);
                break;
                case 'r':
                ret[1]++;
                if (ret[0] < ret[1]) {
                    return -1;
                }
                break;
                case 'o':
                ret[2]++;
                if (ret[1] < ret[2]) {
                    return -1;
                }
                break;
                case 'a':
                ret[3]++;
                if (ret[2] < ret[3]) {
                    return -1;
                }
                break;
                case 'k':
                ret[4]++;
                if (ret[3] < ret[4]) {
                    return -1;
                }
                for (int j = 0; j < 5; j++) {
                    ret[j]--;
                    if (ret[j] < 0) {
                        return -1;
                    }
                }
                break;
            }
        }
        for (int i = 0; i < 5; i++) {
            if (ret[i] != 0) {
                return -1;
            }
        }
        return max;
    }
}
//459
class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int len = timeSeries.length;
        if (len == 1) {
            return duration;
        }
        if (duration == 0) {
            return 0;
        }
        int[] dp1 = new int[len];
        for (int i = 0; i < len; i++) {
            dp1[i] = timeSeries[i] + duration - 1;
        }
        int[] dp2 = new int[len];
        dp2[0] = duration;
        int star = 0;
        for (int i = 1; i < len; i++) {
            if (timeSeries[i] <= dp1[i-1]) {
                dp2[i] = dp1[i] - dp1[star] + dp2[i-1];
            }
            else {
                dp2[i] = dp2[i-1] + duration;
            }
            star = i;
        }
        return dp2[len-1];
    }
}
//6
class Solution {
    public String convert(String s, int numRows) {
        List<List<Character>> list = new ArrayList<>();
        int len = s.length();
        for (int i = 0; i < numRows; i++) {
            list.add(new ArrayList<>());
        }
        int row = 0;
        for (int i = 0; i < len; ) {
            row = 0;
            while (row < numRows && i < len) {
                list.get(row++).add(s.charAt(i++));
            }
            row -= 2;
            while (row > 0 && i < len) {
                list.get(row--).add(s.charAt(i++));
            }

        }
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < list.get(i).size(); j++) {
                str.append(list.get(i).get(j));
            }
        }
        return str.toString();
    }
}
//38
class Solution {
    public String countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        return desc(countAndSay(n-1));
    }

    public String desc(String str) {
        String ret = "";
        int len = str.length();
        char tmp = '1';
        for (int i = 0; i < len; i++) {
            if (i != 0) {
                if (str.charAt(i) != str.charAt(i-1)) {
                    ret += tmp;
                    ret += str.charAt(i-1);
                    tmp = '1';
                }
                else {
                    tmp = (char)(tmp + 1);
                }
            }
        }
        ret += tmp;
        ret += str.charAt(len-1);
        return ret;
    }
}